package com.gitee.wsl.ext.array.sort

import com.gitee.wsl.ext.array.swap
import com.gitee.wsl.ext.base.Arrays.arraycopy
import com.gitee.wsl.ext.base.Integer
import kotlin.math.max
import kotlin.math.min


class HeapSort {
    private var array = emptyArray<Int>()
    private var nextIndex = 0

    fun peekArray() = array.copyOf(array.size)

    fun add(element: Int) {
        if (array.isEmpty() || nextIndex > array.lastIndex) {
            growArray()
        }
        array[nextIndex] = element
        bubbleUp(nextIndex)
        nextIndex++
    }

    private fun growArray() {
        // Size is always index + 1
        val temp = Array(nextIndex + 1) { 0 }
        arraycopy(array, 0, temp, 0, array.size)
        array = temp
    }

    private fun shrinkArray() {
        val temp = Array(array.size - 1) { 0 }
        arraycopy(array, 0, temp, 0, array.size - 1)
        array = temp
        nextIndex--
    }

    private fun bubbleUp(index: Int) {
        var currentIndex = index
        var parentIndex = parentIndexOfIndex(currentIndex)
        while (currentIndex != parentIndex && array[parentIndex] > array[currentIndex]) {
            swap(parentIndex, currentIndex)
            currentIndex = parentIndex
            parentIndex = parentIndexOfIndex(currentIndex)
        }
    }

    private fun swap(from: Int, to: Int) {
        println("Swapping index:$from-->$to; value:${array[from]}-->${array[to]}")
        val temp = array[from]
        array[from] = array[to]
        array[to] = temp
    }

    private fun parentIndexOfIndex(index: Int): Int = if (index % 2 == 0) max(0, index / 2 - 1) else index / 2

    private fun indexOfLeftChildOfIndex(index: Int): Int = index * 2 + 1

    private fun indexOfRightChildOfIndex(index: Int): Int = index * 2 + 2

    fun print() = println(array.toString())

    fun peekMinValue() = array[0]

    fun deleteMin() {
        // Bring right most element to the root
        swap(0, array.lastIndex)
        // Delete the last element
        shrinkArray()
        // then bubble root element down
        bubbleDown()
    }

    private fun bubbleDown() {
        var currentIndex = 0
        while (currentIndex < array.size) {
            val leftIndex = indexOfLeftChildOfIndex(currentIndex)
            val rightIndex = indexOfRightChildOfIndex(currentIndex)
            // Left index is filled first so it must be less than last index
            if (leftIndex > array.lastIndex) {
                break
            }
            val leftValue = array[leftIndex]
            val rightValue = array.getOrNull(rightIndex) ?: Integer.MAX_VALUE

            // WARNING: MUST compare with both left and right node and swap with the minimum
            val minValue = min(leftValue, rightValue)

            // Satisfactory position
            if (minValue >= array[currentIndex]) {
                break
            }

            if (minValue == leftValue) {
                // swap with left
                swap(leftIndex, currentIndex)
                currentIndex = leftIndex
            } else if (minValue == rightValue) {
                // swap with right
                swap(rightIndex, currentIndex)
                currentIndex = rightIndex
            } else {
                break
            }
        }
    }
}

/**
 * Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure.
 * It divides the input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region
 * by extracting the largest element from it and inserting it into the sorted region. The algorithm
 * efficiently builds a max heap on the input array to facilitate the extraction of maximum elements.
 *
 * Worst-case performance:       O(n log n)
 * Best-case performance:        O(n log n)
 * Average performance:          O(n log n)
 * Worst-case space complexity:  O(1)
 */
fun<T : Comparable<T>> Array<T>.heapSort(){
    val size = this.size
    for (i in size / 2 - 1 downTo 0) {
        heapify(this, size, i)
    }

    for (i in size - 1 downTo 0) {
        this.swap(0, i)
        heapify(this, i, 0)
    }
}

/**
 * Performs heapify operation on the array.
 *
 * @param array The array to heapify.
 * @param size The size of the heap.
 * @param index The index of the current element in the heap.
 * @param T The type of elements in the array, must be comparable.
 */
@Suppress("SAY_NO_TO_VAR")
private fun <T : Comparable<T>> heapify(
    array: Array<T>,
    size: Int,
    index: Int,
) {
    var largest = index
    val left = 2 * index + 1
    val right = 2 * index + 2

    if (left < size && array[left] > array[largest]) {
        largest = left
    }

    if (right < size && array[right] > array[largest]) {
        largest = right
    }

    if (largest != index) {
        array.swap(index, largest)
        heapify(array, size, largest)
    }
}